package com.dubious.interview.euler;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import org.joda.time.DateTime;

/**
 * By starting at the top of the triangle below and moving to adjacent numbers on the row below, the
 * maximum total from top to bottom is 23.
 * 
 * 3 7 4 2 4 6 8 5 9 3
 * 
 * That is, 3 + 7 + 4 + 9 = 23.
 * 
 * Find the maximum total from top to bottom of the triangle below:
 * 
 * - snip -
 */
public class Problem18 {

    public static void main(String[] args) throws IOException {
        // this problem seems to be solvable by dynamic programming
        System.out.println("Start time: " + new DateTime());

        System.out.println("Max value: " + getMaximumPathInTriangle("input/euler/Problem18.in"));
        // 1074
        System.out.println("End time: " + new DateTime());
        // in 105 ms
    }

    public static long getMaximumPathInTriangle(String triangleFile) throws IOException {
        // read the lines from file into arrays
        BufferedReader reader =
                new BufferedReader(new InputStreamReader(new FileInputStream(triangleFile)));
        List<int[]> values = new ArrayList<int[]>();
        String line = null;
        while ((line = reader.readLine()) != null) {
            String[] splits = line.split(" ", 0);
            int[] lineValues = new int[splits.length];

            for (int i = 0; i < splits.length; i++) {
                lineValues[i] = Integer.parseInt(splits[i]);
            }

            values.add(lineValues);
        }

        // generate a two dimensional array that will hold the dynamic results
        long[][] results = new long[values.size()][values.size()];

        //@formatter:off
        // here is an example triangle:
        // 00
        // 01 05 
        // 08 14 11
        // 01 01 12 03
        // 
        // with result:
        // 00
        // 01 05
        // 09 19 16
        // 10 20 31 19 
        //
        // note that r(i,j) = max(r(i-1,j-1), r(i-1,j)) + v(i,j)
        //@formatter:on

        // dynamically calculate the results throughout
        for (int i = 0; i < values.size(); i++) {
            for (int j = 0; j <= i; j++) {
                if (i == 0) {
                    results[i][j] = values.get(i)[j];
                } else if (j == 0) {
                    // on left most element of row
                    results[i][j] = values.get(i)[j] + results[i - 1][j];
                } else if (j == i) {
                    // on right most element of row
                    results[i][j] = values.get(i)[j] + results[i - 1][j - 1];
                } else {
                    results[i][j] =
                            values.get(i)[j]
                                    + Math.max(results[i - 1][j], results[i - 1][j - 1]);
                }
            }
        }

        // now iterate over the entries in the last row and find the maximum
        long maxValue = 0;
        for (int i = 0; i < values.size(); i++) {
            if (results[values.size() - 1][i] > maxValue) {
                maxValue = results[values.size() - 1][i];
            }
        }

        return maxValue;
    }
}
